package src.BlueBridge.GreedyStrategyAndDynamicProgramming;

/**
    数字三角形

    在数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大
    路径上的每一步都只能往左下或者往右下走，只需要求出这个最大和即可，不必给出具体路径
    三角形的行数大于1小于等于100 数字为0-99
    输入格式:5 表示三角形的行数 接下来输入三角形
        7
       3 8
      8 1 0
     2 7 4 4
    4 5 2 6 5
    要求输出最大和

    要分析依赖
 */

public class _12数字三角形 {
    public static void main(String[] args) {
        int[][] triangle = {
                {7},
                {3, 8},
                {8, 1, 0},
                {2, 7, 4, 4},
                {4, 5, 2, 6, 5}
        };
        int ans = maxSumUsingRecursive(triangle, 0, 0);
        System.out.println(ans);
        ans = maxSumUsingDp(triangle, 0, 0);
        System.out.println(ans);
    }

    /**
     * dfs解法
     * @param triangle 数字三角形
     * @param i 起点行号
     * @param j 起点列号
     * @return 计算出的最大和
     */
    public static int maxSumUsingRecursive(int[][] triangle, int i, int j) {
        // 当前三角形的行数
        int rowIndex = triangle.length;
        if (i == rowIndex - 1) {
            return triangle[i][j];
        }else {
            // 顶点的值+max(左侧支线的最大值,右侧支路的最大值)
            return triangle[i][j] + Math.max(maxSumUsingRecursive(triangle, i + 1, j),
                    maxSumUsingRecursive(triangle, i + 1, j + 1));
        }
    }

    /*
    dp解法，由下至上，使用一个二维数组(反着看)
    4 5 2 6 5
    5 12 10 10
    20 13 10
    23 21
    30
    从而dp[0][0]就是我们要的结果
     */
    public static int maxSumUsingDp(int[][] triangle, int i, int j) {
        // 行数
        int rowCount = triangle.length;
        // 最后一行的列数
        int columnCount = triangle[rowCount - 1].length;
        // 创建dp表格 打表
        int[][] dp = new int[rowCount][columnCount];
        // 初始化最后一行 与原三角形二维数组最后一行相同
        for (int k = 0 ; k < columnCount ; k++) {
            dp[rowCount - 1][k] = triangle[rowCount - 1][k];
        }
        // 倒着打表
        for (int k = rowCount - 2 ; k >= 0 ; k--) {
            for (int l = 0 ; l <= k ; l++) {
                dp[k][l] = triangle[k][l] + Math.max(dp[k + 1][l], dp[k + 1][l + 1]);
            }
        }
        return dp[0][0];
    }
}
